package guide;

import common.DoubleNode;
import common.ListNode;
import common.TreeNode;
import org.junit.Test;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author fance
 * @date 18-5-1 上午9:54
 */
public class ListSum {

    /**
     * 打印两个有序链表的公共部分
     * @param head1
     * @param head2
     */
    public void printCommonPart(ListNode head1, ListNode head2) {
        ListNode tmp1 = head1;
        ListNode tmp2 = head2;
        while (tmp1 != null && tmp2 != null) {
            if (tmp1.val < tmp2.val) {
                tmp1 = tmp1.next;
            } else if (tmp1.val > tmp2.val) {
                tmp2 = tmp2.next;
            } else {
                System.out.print(head1.val + " ");
                tmp1 = tmp1.next;
                tmp2 = tmp2.next;
            }
        }
    }


    /**
     *  删除倒数第k个节点
     * @param head
     * @param k
     * @return
     */
    public ListNode removeLastKthNode(ListNode head, int k) {
        if (head == null || k < 1) {
            return head;
        }
        ListNode cur = head;
        // 每走一步,k-- 到末尾  k = k - n;
        while (cur != null) {
            k--;
            cur = cur.next;
        }
        if (k == 0) {
            head = head.next;
        }

        // ++k 到0 时停止,  此时停在n - k 位置.即要删除的节点前一个节点
        if (k < 0) {
            cur = head;
            while (++k != 0) {
                cur = cur.next;
            }
            cur.next = cur.next.next;
        }
        return head;
    }
    public DoubleNode removeLastKthNode(DoubleNode head, int k) {
        if (head == null || k < 1) {
            return head;
        }
        DoubleNode cur = head;
        while (cur != null) {
            k--;
            cur = cur.next;
        }
        if (k == 0) {
            head = head.next;
            head.prev = null;
        }
        if (k < 0) {
            cur = head;
            while (++k != 0) {
                cur = cur.next;
            }
            DoubleNode newNext = cur.next.next;
            cur.next = newNext;
            if (newNext != null) {
                newNext.prev = cur;
            }
        }
        return head;
    }

    /**
     * 反转链表
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode next = null;
        while (head != null) {
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
    public DoubleNode reverseList(DoubleNode head) {
        DoubleNode pre = null;
        DoubleNode next = null;
        while (head != null) {
            next = head.next;
            head.next = pre;
            head.prev = next;
            pre = head;
            head = next;
        }
        return pre;
    }

    /**
     * 约瑟夫环问题
     * @param head
     * @param m
     * @return
     */
    public ListNode josephusKill(ListNode head, int m) {
        if (head == null || head.next == head || m < 1) {
            return head;
        }
        ListNode last = head;
        while (last.next != null) {
            last = last.next;
        }
        last.next = head;  // 成环。
        int cnt = 0;
        while (head != last) {
            if (++cnt == m) {
                last.next = head.next;
                cnt = 0;
            } else {
                last = last.next;
            }
            head = last.next;
        }
        return head;
    }

    /**
     * 单链表相加  正序保存 需要先反转链表
     * @param head1
     * @param head2
     * @return
     */
    public ListNode addListsII(ListNode head1, ListNode head2) {
        head1 = reverseList(head1);
        head2 = reverseList(head2);
        int carry = 0;
        int n1 = 0;
        int n2 = 0;
        int n = 0;
        ListNode c1 = head1;
        ListNode c2 = head2;
        ListNode node = null;
        ListNode pre = null;
        while (c1 != null || c2 != null) {
            n1 = c1 != null ? c1.val : 0;
            n2 = c2 != null ? c2.val : 0;
            n = n1 + n2 + carry;
            pre = node;
            node = new ListNode(n % 10);
            node.next = pre;
            carry = n / 10;
            c1 = c1 != null ? c1.next : null;
            c2 = c2 != null ? c2.next : null;
        }
        if (carry == 1) {
            pre = node;
            node = new ListNode(1);
            node.next = pre;
        }
        return node;
    }


    /**
     * 链表是否回文
     * @param head
     * @return
     */
    public boolean isPalindromeI(ListNode head) {
        LinkedList<ListNode> stack = new LinkedList<>();
        ListNode cur = head;
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        cur = head;
        while (cur != null) {
            if (cur.val != stack.pop().val) {
                return false;
            }
            cur = cur.next;
        }
        return true;
    }

    /**
     *  二叉搜索树转换为有序双链表  中序遍历
     * @param head
     * @return
     */
    public TreeNode convertToDoubleList(TreeNode head) {
        Queue<TreeNode> queue = new LinkedList<>();
        inOrderToQueue(head,queue);
        if (queue.isEmpty()) {
            return head;
        }
        head = queue.poll();
        TreeNode pre = head;
        pre.left = null;
        TreeNode cur = null;
        while (!queue.isEmpty()) {
            cur = queue.poll();
            pre.right = cur;
            cur.left = pre;
            pre = cur;
        }
        pre.right = null;
        return head;
    }
    private void inOrderToQueue(TreeNode head, Queue<TreeNode> queue) {
        if (head == null) {
            return;
        }
        inOrderToQueue(head.left, queue);
        queue.offer(head);
        inOrderToQueue(head.right, queue);
    }

    @Test
    public void test() {
        ListNode listNode1 = new ListNode(1);
        ListNode listNode2 = new ListNode(2);
        ListNode listNode3 = new ListNode(3);
        listNode1.next = listNode2;
        listNode2.next = listNode3;
        System.out.println(josephusKill(listNode1,2).val);
    }
}
